package teste;

/*
 * @!RadixSortAlgorithm.java
 * By: Alvin Raj
 * Date: 12 August 2002
 * Algorithm adapted from: C++ Data Structures, Nell Dale
 * Additional Comments added by Jason Harrison <harrison@cs.ubc.ca>
 *
 *  Algorithm comments from
 *  http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/radixsort.html
 *
 */
public class RadixSortAlgorithm extends SortAlgorithm {

	// for each of the 10 digits
	private LinkedQueue[] Q = { new LinkedQueue(), // 0
			new LinkedQueue(), // 1
			new LinkedQueue(), // 2
			new LinkedQueue(), // 3
			new LinkedQueue(), // 4
			new LinkedQueue(), // 5
			new LinkedQueue(), // 6
			new LinkedQueue(), // 7
			new LinkedQueue(), // 8
			new LinkedQueue() }; // 9

	// Assumes all positive integers
	// numbDigits is the number of digits in the largest number
	private void sort(int a[], int numDigits) throws Exception {
		int arrayPos;
		// i is the radix
		for (int i = 1; i <= numDigits; i++) {
			arrayPos = 0;
			// Put values into queues according to radix
			// least significant digit first, then second,...
			// first pass sorts on least significant digit
			for (int j = 0; j < a.length; j++) {
				Q[getRadix(a[j], i)].enqueue(a[j]);

			}
			// Collect the queues and put them back into the array
			// queues contain partially sorted lists after first
			// pass -- moving to next significant digit will
			// maintain this ordering.
			for (int j = 0; j < Q.length; j++) {
				while (!Q[j].isEmpty()) {
					a[arrayPos] = Q[j].dequeue();
					arrayPos++;
				}

			}
		}
	}

	public void sort(int a[]) throws Exception {
		// Find the largest entry in a[]
		int max = 0;
		int maxIndex = 0; // JH
		for (int i = 0; i < a.length; i++) {
			if (max < a[i]) {
				max = a[i];
				maxIndex = i; // JH

			}
		}

		int numDigits = 1;
		int temp = 10;
		// compute the max number of digits
		// JH: this could be more easily be computed by using
		// numDigits = (int) log(base10, max)
		while (true) {
			if (max >= temp) {
				numDigits++;
				temp *= 10;
			} else
				break;
		}

		// call the sort
		sort(a, numDigits);
	}

	// returns the radix of the given number
	// EG:
	// 2nd radix of 79981 is 8
	// 1st radix of 79981 is 1
	public static int getRadix(int number, int radix) {
		return (int) (number / Math.pow(10, radix - 1)) % 10;
	}

}
